
public class InterpolationSearch {

    //插值查找
    public int interpolationSearch(int[] arr, int val) {

        int start = 0;
        int end = arr.length - 1;
        double factor = ( (end - start - 0.0 ) / (arr[end] - arr[start]));
        int mid = (int) (start + factor * (val - arr[start]));

        while (start <= end) {
            System.out.println("查找区间：["+start+","+end +"]");
            if (arr[mid] == val) {
                return mid;
            } else if (arr[mid] > val) {
                //往左找
                end = mid - 1;
            }else {
                //往右找
                start = mid + 1;
            }
            factor = ( (end - start - 0.0 ) / (arr[end] - arr[start]));
            mid = (int) (start + factor * (val - arr[start]));
            //算出的mid步骤[start,end]区间中，无法找到~
            if (mid > end || mid < start)
                break;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2,3, 5, 6, 8, 9,10};
        System.out.println(new InterpolationSearch().interpolationSearch(arr, 7));
    }
}
